In many industrial applications versatile vision systems play an essential role. In the area of quality control, the completeness of assemblies has to be tested; in automated manufacturing, machine parts have to be recognized and their position or orientation has to be determined in order to support flexible manipulator control, etc. Usually, only a two-dimensional picture such as a television camera output is available of the scene which comprises the assembly or the machine part to be handled.
An article by L. G. Roberts "Machine perception of three-dimensional solids", published in "Optical and Electrooptical Information Processing" (Eds: J. T. Tippett et al.), MIT Press, Cambridge, Mass., 1968, pp. 159-197, disclosed procedures for the recognition of three-dimensional objects on the basis of two-dimensional photographs. Polygons which are required for the identification have to be found in the picture. A difficulty is that in many pictures, the lines which represent the object and which form polygons are not complete due to noise or spots which cause local interruptions, so that finding the polygons will not be possible.
In U.S. Pat. No. 3,069,654 (Hough), a method and means are disclosed for recognizing complex patterns. It describes the basic procedure for generating a Hough transform of lines in an image which transform is then used for determining location and orientation of the lines in the image; these lines may be traces in a bubble chamber or a handwritten signature. No recognition of objects is considered.
Some suggestions were made for using Hough transforms to recognize objects or mechanical parts. However, these methods require either higher-dimensional Hough transforms (more than 2-D) or some additional knowledge about spatial parameters of the objects (e.g. surface normals or depth information obtained by structured light or range procedures). They require much computational effort.